#include<stdio.h>
#include<stdlib.h>
#define ElemType int
#define Status int
#define OK 1
#define ERROR 0
typedef struct BiNode{
    ElemType data;
    struct BiNode *left;
    struct BiNode *right;
}BiNode,*BiTree;

//创建节点
BiNode* CreateBNode(ElemType e){
    BiNode* T =(BiNode*)malloc(sizeof(BiNode));
    if (T == NULL) {
        printf("内存分配失败\n");
        exit(1);  // 分配失败则退出
    }
    T->data =e;
    T->left=NULL;
    T->right=NULL;
    return T;
}
//
// 插入节点到二叉搜索树
BiNode* insert(BiNode* root, int data) {
    // 如果树为空，直接创建新节点作为根
    if (root == NULL) {
        return CreateBNode(data);
    }

    // 否则递归插入到左子树或右子树
    if (data < root->data) {
        root->left = insert(root->left, data);  // 插入左子树
    } else if (data > root->data) {
        root->right = insert(root->right, data); // 插入右子树
    }
    // 注意：这里忽略重复值（若需要处理重复值，可根据需求修改）
    return root;
}
// 前序遍历：根 → 左 → 右
void preOrder(BiNode* root) {
    if (root != NULL) {
        printf("%d ", root->data);  // 访问根节点
        preOrder(root->left);       // 遍历左子树
        preOrder(root->right);      // 遍历右子树
    }
}

// 中序遍历：左 → 根 → 右（二叉搜索树的中序遍历是升序的）
void inOrder(BiNode* root) {
    if (root != NULL) {
        inOrder(root->left);        // 遍历左子树
        printf("%d ", root->data);  // 访问根节点
        inOrder(root->right);       // 遍历右子树
    }
}

// 后序遍历：左 → 右 → 根
void postOrder(BiNode* root) {
    if (root != NULL) {
        postOrder(root->left);      // 遍历左子树
        postOrder(root->right);     // 遍历右子树
        printf("%d ", root->data);  // 访问根节点
    }
}

// 释放二叉树所有节点内存
void freeTree(BiNode* root) {
    if (root != NULL) {
        freeTree(root->left);   // 先释放左子树
        freeTree(root->right);  // 再释放右子树
        free(root);             // 最后释放当前节点
    }
}

int main() {
    BiNode* root = NULL;  // 初始化空树

    // 插入节点构建二叉树
    root = insert(root, 50);
    insert(root, 30);
    insert(root, 70);
    insert(root, 20);
    insert(root, 40);
    insert(root, 60);
    insert(root, 80);

    // 遍历输出
    printf("前序遍历: ");
    preOrder(root);  // 50 30 20 40 70 60 80
    printf("\n");

    printf("中序遍历: ");
    inOrder(root);   // 20 30 40 50 60 70 80（升序）
    printf("\n");

    printf("后序遍历: ");
    postOrder(root); // 20 40 30 60 80 70 50
    printf("\n");

    // 释放内存
    freeTree(root);
    return 0;
}